home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Applications / Misc / Crossword / Source / DepthFirstSearch.m < prev    next >
Text File  |  1993-04-13  |  2KB  |  108 lines
  1. /*
  2.  
  3. File DepthFirstSearch.m
  4.  
  5. This search is a standard depth first one.  At each step, the variable with the highest efficiency is selected and filled.  The search backtracks when a variable has no remaining values.
  6.  
  7. It is the responsibility of the variables to implement any special heuristics like backjumping and leapfrogging.
  8.  
  9. */
  10.  
  11. #import <appkit/appkit.h>
  12.  
  13. #import "DepthFirstSearch.h"
  14.  
  15.  
  16. /* ————————————————————————————————————————————————————————————————————————————  */
  17.  
  18.  
  19. #define variable(i)        ([variables  objectAt: i])
  20.  
  21.  
  22. /* ————————————————————————————————————————————————————————————————————————————  */
  23.  
  24.  
  25. @implementation DepthFirstSearch
  26.  
  27.  
  28. - (BOOL) startSearch: (id) theVariables
  29. {
  30.     variables = theVariables;
  31.     next = 0;
  32.     ok = YES;
  33.     last = nil;
  34.     count = [variables  count];
  35.     
  36.     return [self  continue];
  37. }
  38.  
  39.  
  40. - (BOOL) continue
  41. {
  42.     while ([NXApp    getNextEvent: NX_KEYDOWNMASK
  43.                     waitFor: 0
  44.                     threshold: NX_MODALRESPTHRESHOLD] == NULL)
  45.         
  46.         if ([self  step] == NO) return NO;
  47.     
  48.     return YES;
  49. }
  50.  
  51.  
  52. - (BOOL) step
  53. {
  54.     if (ok) [self  findBest];
  55.     ok = [self  fill: variable(next)];
  56.     
  57.     if (!ok && (next-- == 0)) return [self  done];
  58.     else if (ok && (++next == count)) return [self  done];
  59.     else return YES;
  60. }
  61.  
  62.  
  63. - (BOOL) done
  64. {
  65.     [last  unhilight];
  66.     return NO;
  67. }
  68.  
  69.  
  70. - (BOOL) fill: (id) variable
  71. {
  72.     BOOL    status;
  73.     
  74.     [last  unhilight];
  75.     [variable  hilight];
  76.     status = [last = variable  fillNext];
  77.     
  78.     return status;
  79. }
  80.  
  81.  
  82. /* ————————————————————————————————————————————————————————————————————————————  */
  83.  
  84.  
  85. - findBest
  86. {
  87.     float    value, current;
  88.     int        best, i;
  89.     id        temp;
  90.     
  91.     for (best = 0, value = -1.0, i = next; i < count; i++)
  92.     {
  93.         if ((current = [variable(i)  efficiency]) > value)
  94.         {
  95.             value = current;
  96.             best = i;
  97.         }
  98.     }
  99.     
  100.     temp = variable(next);
  101.     [variables  replaceObjectAt: next  with: variable(best)];
  102.     [variables  replaceObjectAt: best  with: temp];
  103.     
  104.     return self;
  105. }
  106.  
  107.  
  108. @end